A network system is formed from communication devices that deliver data packets originated from terminal devices to their respective destinations over communication links. Conventionally, those communication devices include internal buffer storage to prevent congestion and enhance the efficiency of data transfer. Since the data capacity of a buffer is not infinite, an overwhelming amount of incoming packets would clog up the buffer, resulting in a loss of subsequent packets.
As an example of a conventional technique, Japanese Laid-open Patent Publication No. 2006-135762 proposes a packet transmission device having a front-end traffic policer that monitors and controls the amount of incoming packets by discarding some of them before they are entered to a buffer. The proposed technique enables priority-based data buffering, which prevents the buffer from being occupied by low-priority data. The proposed technique also offers priority-based scheduling of packet traffic, as well as a service with a guaranteed bandwidth defined in terms of “committed information rate” (CIR), the minimum transmission rate guaranteed even in the event of network congestion.
As another example of a conventional technique, Japanese Laid-open Patent Publication No. 2003-188912 proposes a method for controlling buffers. According to this publication, data stored in a buffer will be discarded if the length of a data queue exceeds a threshold.
As yet another example of a conventional technique, Japanese Laid-open Patent Publication No. 4-257145 (1992) proposes a communication control device that observes the amount of incoming packet flow for each logical channel signal. The proposed device puts a mark on a packet if its data size exceeds a first threshold defined on the basis of the sending subscriber's declaration. Further, the proposed device discards packets if the packet flow exceeds a second threshold, which is greater than the first threshold.
As still another example of a conventional technique, Japanese Laid-open Patent Publication No. 2007-65948 proposes a buffer memory device with a double buffer structure. Data is written in one buffer at a first operating frequency, while another buffer outputs data at a second operating frequency to transfer the data to a FIFO memory.
As a further example of a conventional technique, Japanese Laid-open Patent Publication No. 2007-134936 proposes a DMA controller that measures a time overhead of a data transfer operation when transferring received packets to a buffer. If the observed time overhead is greater than a threshold, the DMA controller cancels the data transfer.
The above-described approach using a front-end policer, however, may increase the cost of communication devices because a large amount of circuitry is necessary to implement it. But simply abandoning a front-end bandwidth control mechanism means allowing any class of packets to enter the buffer without control. As a result, the buffer could be occupied by low-priority packets, failing to satisfy a specified CIR of high-priority packets.
FIG. 34 illustrates a case where a guaranteed CIR may not be maintained in a conventional system because of its lack of packet discard functions. The illustrated conventional station 90 has a write controller 92 and a packet buffer 93, but no mechanisms for discarding packets (data). Accordingly, every packet that has arrived at the station 90 will later be transmitted unless the packet buffer 93 encounters overflow.
That is, the illustrated station 90 allows incoming packets to go straight into the packet buffer 93 without limit, in the order that they have arrived. The received packets accumulate in the packet buffer 93 without being discarded until its maximum capacity is reached. Once the capacity limit is hit, the subsequent packets will be lost.
Basically the packet buffer 93 never experiences overflow in the case where the output rate of packets is equal to or higher than the input rate of same. But in the case where the input rate exceeds the output rate, excessive incoming packets will overflow the packet buffer 93, resulting in a loss of packets.
Another problem is that the station 90 is unable to provide priority-based scheduling on the output side or to guarantee the bandwidth for specified CIR. This is because the station's input interface sends received packets to the packet buffer 93 simply in the order of arrival, regardless of their priorities.
The above-noted problems arise in at least the following two conditions:
(a) Input Link Bandwidth>Output Link Bandwidth
This condition causes accumulation of data in the buffer.
(b) Lack of Policing Functions for Input Packets
Without packet policers or other discard mechanisms to control input bandwidths based on the priority of traffic, the buffer has to accept all incoming packets in the order that they arrive. The buffer may be occupied by low-priority data, and when this happens, output policing is useless in transmitting high-priority packets in preference to other packets to maintain a guaranteed CIR. This issue will be discussed in detail below.
Now let “class C” and “class D” represent two different priority classes, where class C has a higher priority over class D. The station has a scheduler that achieves output policing to guarantee the CIR of class-C traffic by reading buffer data of class-C packets in preference to class-D packets. However, the above-noted conditions (a) and (b) allow a burst of class-D packets to occupy the buffer. In such a case, the scheduler placed at the buffer output cannot read out high-priority, class-C packets at a sufficient rate. Accordingly, the overstuffed buffer begins to reject newly received class-C packets, resulting in a loss of high-priority packets. In other words, the conditions (a) and (b) paralyzes the scheduler and thus invites degradation of CIR or other problems.
Referring again to FIG. 34, a more specific example will be described below. Suppose now that the station 90 receives both class-C packets and class-D packets at the rate of 100 Mbps for each. The total incoming traffic thus amounts to 200 Mbps. Also suppose that the station 90 has to offer a CIR of 100 Mbps for class-C traffic and that of 50 Mbps for class-D traffic. It is assumed that the output link bandwidth is 150 Mbps. Again, class-C packets have a higher priority over class-D packets.
Note that input bandwidth is greater than output bandwidth in the present example. Accordingly, the amount of packets stored in the packet buffer 93 increases with time. More precisely, the amount of class-C packets in the packet buffer 93 does not change because the input and output bandwidths of class C are both 100 Mbps. It is the class-D packets that actually increases in the packet buffer 93. Since the class-D traffic has a larger input bandwidth than its output bandwidth, class-D packets gradually consume free space of the packet buffer 93 and eventually causes a buffer overflow.
Once the overflow level is reached, the packet buffer 93 can only produce a limited free space for a new frame each time a stored packet is read out. The produced space is used by a packet received at the moment when that space becomes available.
The present example assumes that class-C and class-D packets have the same frame length, and that they enter the packet buffer 93 evenly over time. It is also assumed that the packet buffer 93 accepts class-C packets at a probability of 50 percent on average. Received class-C packets make their way to the packet buffer 93, together with received class-D packets, and those packets are permitted to enter the packet buffer 93 at 50% probability. The remaining packets are lost. Also, the survived class-C packets can only have at most 50% of the output bandwidth of the station 90. Since, as mentioned above, the output link bandwidth is 150 Mbps, the output rate of class-C packets will be 75 Mbps (=150/2). This means that the station 90 cannot satisfy the specified CIR of class C, which is 100 Mbps. On the other hand, the remaining output bandwidth is used by the class-D packet traffic, meaning that class-D packets are transmitted at 75 Mbps, which is well above the guaranteed CIR of class D.
The above result is based on a simple probability model, and the actual behavior of a station may vary depending on the packet lengths and other specific conditions. In some implementations, the station handles packets having different lengths and different priorities. Conventional stations are likely to experience the above-noted problems of CIR degradation in such circumstances.